Counting in Trees for Free
Identifieur interne : 000871 ( France/Analysis ); précédent : 000870; suivant : 000872Counting in Trees for Free
Auteurs : Helmut Seidl [Allemagne] ; Thomas Schwentick [Allemagne] ; Anca Muscholl [France] ; Peter Habermehl [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2004.
Abstract
Abstract: It is known that MSO logic for ordered unranked trees is undecidable if Presburger constraints are allowed at children of nodes. We show here that a decidable logic is obtained if we use a modal fixpoint logic instead. We present a characterization of this logic by means of deterministic Presburger tree automata and show how it can be used to express numerical document queries. Surprisingly, the complexity of satisfiability for the extended logic is asymptotically the same as for the original fixpoint logic. The non-emptiness for Presburger tree automata (PTA) is pspace-complete, which is moderate given that it is already pspace-hard to test whether the complement of a regular expression is non-empty. We also identify a subclass of PTAs with a tractable non-emptiness problem. Further, to decide whether a tree t satisfies a formula ϕ is polynomial in the size of ϕ and linear in the size of t. A technical construction of independent interest is a linear time construction of a Presburger formula for the Parikh image of a regular language.
Url:
DOI: 10.1007/978-3-540-27836-8_94
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001618
- to stream Istex, to step Curation: 001618
- to stream Istex, to step Checkpoint: 000861
- to stream Main, to step Merge: 001D53
- to stream Main, to step Curation: 001C98
- to stream Main, to step Exploration: 001C98
- to stream France, to step Extraction: 000871
Links to Exploration step
ISTEX:2925B247C35146C3B5900B70460EC7B25A4CFE36Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Counting in Trees for Free</title><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></author><author><name sortKey="Schwentick, Thomas" sort="Schwentick, Thomas" uniqKey="Schwentick T" first="Thomas" last="Schwentick">Thomas Schwentick</name></author><author><name sortKey="Muscholl, Anca" sort="Muscholl, Anca" uniqKey="Muscholl A" first="Anca" last="Muscholl">Anca Muscholl</name></author><author><name sortKey="Habermehl, Peter" sort="Habermehl, Peter" uniqKey="Habermehl P" first="Peter" last="Habermehl">Peter Habermehl</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:2925B247C35146C3B5900B70460EC7B25A4CFE36</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-27836-8_94</idno><idno type="url">https://api.istex.fr/document/2925B247C35146C3B5900B70460EC7B25A4CFE36/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001618</idno><idno type="wicri:Area/Istex/Curation">001618</idno><idno type="wicri:Area/Istex/Checkpoint">000861</idno><idno type="wicri:doubleKey">0302-9743:2004:Seidl H:counting:in:trees</idno><idno type="wicri:Area/Main/Merge">001D53</idno><idno type="wicri:Area/Main/Curation">001C98</idno><idno type="wicri:Area/Main/Exploration">001C98</idno><idno type="wicri:Area/France/Extraction">000871</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Counting in Trees for Free</title><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><wicri:noCountry code="subField">I2</wicri:noCountry></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Schwentick, Thomas" sort="Schwentick, Thomas" uniqKey="Schwentick T" first="Thomas" last="Schwentick">Thomas Schwentick</name><affiliation><wicri:noCountry code="subField">niversität Marburg</wicri:noCountry></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Muscholl, Anca" sort="Muscholl, Anca" uniqKey="Muscholl A" first="Anca" last="Muscholl">Anca Muscholl</name><affiliation wicri:level="3"><country>France</country><placeName><settlement type="city">Paris</settlement><region type="région" nuts="2">Île-de-France</region></placeName><wicri:orgArea>LIAFA, Université Paris 7, 2, pl. Jussieu, F-75251</wicri:orgArea></affiliation></author><author><name sortKey="Habermehl, Peter" sort="Habermehl, Peter" uniqKey="Habermehl P" first="Peter" last="Habermehl">Peter Habermehl</name><affiliation wicri:level="3"><country>France</country><placeName><settlement type="city">Paris</settlement><region type="région" nuts="2">Île-de-France</region></placeName><wicri:orgArea>LIAFA, Université Paris 7, 2, pl. Jussieu, F-75251</wicri:orgArea></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2004</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">2925B247C35146C3B5900B70460EC7B25A4CFE36</idno><idno type="DOI">10.1007/978-3-540-27836-8_94</idno><idno type="ChapterID">Chap94</idno><idno type="ChapterID">94</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: It is known that MSO logic for ordered unranked trees is undecidable if Presburger constraints are allowed at children of nodes. We show here that a decidable logic is obtained if we use a modal fixpoint logic instead. We present a characterization of this logic by means of deterministic Presburger tree automata and show how it can be used to express numerical document queries. Surprisingly, the complexity of satisfiability for the extended logic is asymptotically the same as for the original fixpoint logic. The non-emptiness for Presburger tree automata (PTA) is pspace-complete, which is moderate given that it is already pspace-hard to test whether the complement of a regular expression is non-empty. We also identify a subclass of PTAs with a tractable non-emptiness problem. Further, to decide whether a tree t satisfies a formula ϕ is polynomial in the size of ϕ and linear in the size of t. A technical construction of independent interest is a linear time construction of a Presburger formula for the Parikh image of a regular language.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>France</li></country><region><li>Île-de-France</li></region><settlement><li>Paris</li></settlement></list><tree><country name="Allemagne"><noRegion><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></noRegion><name sortKey="Schwentick, Thomas" sort="Schwentick, Thomas" uniqKey="Schwentick T" first="Thomas" last="Schwentick">Thomas Schwentick</name></country><country name="France"><region name="Île-de-France"><name sortKey="Muscholl, Anca" sort="Muscholl, Anca" uniqKey="Muscholl A" first="Anca" last="Muscholl">Anca Muscholl</name></region><name sortKey="Habermehl, Peter" sort="Habermehl, Peter" uniqKey="Habermehl P" first="Peter" last="Habermehl">Peter Habermehl</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/OperaV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000871 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000871 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= OperaV1
|flux= France
|étape= Analysis
|type= RBID
|clé= ISTEX:2925B247C35146C3B5900B70460EC7B25A4CFE36
|texte= Counting in Trees for Free
}}
| This area was generated with Dilib version V0.6.21. |  |